#define _CRT_SECURE_NO_WARNINGS 1
#include "mheap.h"
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->_a = NULL;
	hp->_size = 0;
	hp->_capacity = 0;
}
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_size = 0;
	hp->_capacity = 0;
}
void swap(HPDataType* pch, HPDataType* ppr)
{
	assert(pch);
	assert(ppr);
	HPDataType h = *pch;
	*pch = *ppr;
	*ppr = h;
}
void adjustup(HPDataType* pa, int size)
{
	assert(pa);
	int ch = size-1;
	int pr = (ch - 1) / 2;
	while (ch!=0)
	{
		if (pa[ch] > pa[pr])
		{
			swap(&pa[ch], &pa[pr]);
			ch = pr;
			pr = (ch - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->_size == hp->_capacity)
	{
		int n=hp->_capacity == 0 ? 4 : 2 * (hp->_capacity);
		HPDataType* tm = (HPDataType*)realloc(hp->_a, n * sizeof(HPDataType));
		if (tm == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->_capacity = n;
		hp->_a = tm;
	}
	hp->_a[hp->_size] = x;
	hp->_size++;
	adjustup(hp->_a, hp->_size);
}
void adjustdown(HPDataType* pa, int size,int pr)
{
	assert(pa);
	int ch = pr * 2 + 1;
	while (ch <size)
	{
		HPDataType* huan = &pa[ch];
		if (ch+1<size&&pa[ch] < pa[ch + 1])
		{
			huan = &pa[ch + 1];
			ch++;
		}
		if (*huan > pa[pr])
		{
			swap(huan, &pa[pr]);
			pr = ch;
			ch = pr * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->_size > 0);
	swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	hp->_size--;
	adjustdown(hp->_a, hp->_size,0);
}
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->_size > 0);
	return hp->_a[0];
}
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}
int HeapEmpty(Heap* hp)
{
	assert(hp);
	if (hp->_size == 0)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}